class Solution {
public:
    int maxTotalReward(vector<int>& r) {
        // 排序
        sort(r.begin(), r.end());

        // dp[i][j] 表示从前 i 个物品中选，分数能否达到 j
        // j 的最大值为最大的数的两倍
        int n = r.size(), m = r[n - 1] * 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(m, false));

        // 初始化
        dp[0][0] = true;

        // 填表
        for(int i = 1; i <= n; i++)
        {
            int x = r[i - 1];
            for(int j = 0; j < m; j++)
            {
                dp[i][j] = dp[i - 1][j];    // 不选 r[i] 这个数

                if(j >= x && j < x * 2)
                    dp[i][j] = dp[i][j] | dp[i - 1][j - x];
            }
        }

        // 返回值
        for(int j = m - 1; j >= 0; j--)
            if(dp[n][j])
                return j;
        return -1;
    }
};